package net.dodoman.sort;

public class SorterOther {
	
	public static void main(String[] args) {
		int gohome[] = new int[] { 12, 7, 54, 21, 1, 4, 65, 76, 34, 9, 3, 6 };
		System.out.println("插入排序算法");
		InsertionSort(gohome);
		System.out.println("-------------------------------------------");
		System.out.println("选择排序算法");
		SelectSort(gohome);
		System.out.println("-------------------------------------------");
		System.out.println("冒泡排序算法");
		BubbleSort(gohome);
		System.out.println("-------------------------------------------");
		gohome = QuickSort(gohome);

		for (int t = 0; t < gohome.length; t++) {
			System.out.print(gohome[t] + "--");
		}
	}

	// 插入排序算法
	public static void InsertionSort(int[] goal) {
		for (int i = 1; i < goal.length; i++) {
			int now = i;
			int frank = goal[i];
			while (now > 0 && goal[now - 1] <= frank) {
				goal[now] = goal[now - 1];
				now--;
			}
			goal[now] = frank;

		}
		for (int t = 0; t < goal.length; t++) {
			System.out.print(goal[t] + "--");
		}
	}

	// 选择排序算法
	public static void SelectSort(int[] goal) {
		int max;
		int stmp;
		for (int i = 0; i < goal.length - 1; i++) {
			max = i;
			for (int j = i + 1; j < goal.length; j++)
				if (goal[j] > goal[max])
					max = j;

			stmp = goal[i];
			goal[i] = goal[max];
			goal[max] = stmp;
		}
		for (int t = 0; t < goal.length; t++) {
			System.out.print(goal[t] + "--");
		}

	}

	// 冒泡排序算法
	public static void BubbleSort(int[] goal) {
		int stmp;
		for (int i = 1; i < goal.length; i++) {
			for (int j = 0; j < i; j++) {
				if (goal[i] > goal[j]) {
					stmp = goal[i];
					goal[i] = goal[j];
					goal[j] = stmp;
				}
			}
		}
		for (int t = 0; t < goal.length; t++) {
			System.out.print(goal[t] + "--");
		}
	}

	// 快速排序算法
	public static int[] QuickSort(int[] number) {
		QuickSort(number, 0, number.length - 1);
		return number;
	}

	private static void QuickSort(int[] number, int left, int right) {
		int stmp;
		if (left < right) {
			System.out.println(left + " | " + right + " | " + (left + right)
					/ 2);
			int s = number[(left + right) / 2];
			int i = left - 1;
			int j = right + 1;
			while (true) {
				// 向右找
				while (number[++i] > s)
					;
				// 向左找
				while (number[--j] < s)
					;
				if (i >= j)
					break;
				stmp = number[i];
				number[i] = number[j];
				number[j] = stmp;
			}
			QuickSort(number, left, i - 1); // 对左边进行递回
			QuickSort(number, j + 1, right); // 对右边进行递回
		}
	}
}
